\section{Fundamentação Teórica}
\label{fundamentacao}

Nesta seção, são apresentados os conceitos necessários ao entendimento das técnicas utilizadas para o desenvolvimento da solução proposta: algoritmos genéticos e busca gulosa.

\subsection{Algoritmo Genético}

O algoritmo genético (AG) é um algoritmo de busca local baseado nos mecanismos de seleção natural, em que os indivíduos que representam uma melhor solução sobrevivem. O AG mantém uma população de estruturas (indivíduos), que representam possíveis soluções para o problema e esta população é modificada a cada iteração (geração). Cada indivíduo é composto de genes, e cada gene representa uma característica do indivíduo da população. De acordo com \cite{goes} a estrutura dos AG é a baseada nos seguintes passos:

\begin{enumerate}
 \item Iniciar a população e o número de gerações;
 \item Calcular o \textit{fitness} da população;
 \item Iniciar uma nova geração, selecionando os indivíduos para o próximo passo;
 \item Aplicar os operadores genéticos;
 \item Calcular o \textit{fitness} da população resultante;
 \item Selecionar os melhores indivíduos da solução inicial e da solução resultante;
 \item Avaliar a solução a partir do critério de parada (parar AG ou voltar para o passo 3).
\end{enumerate}

Existem três tipos básicos de modificações (operadores genéticos) que podem ocorrer na população \cite{goes}: cruzamentos, mutações e inversão. Após cada iteração a população é avaliada através de uma \textit{função de fitness} que classifica os indivíduos de acordo com as regras que são satisfeitas. Há duas formas bastante conhecidas para seleção dos indivíduos para uma próxima geração ou para cruzamento: a utilização de um mecanismo de roleta ou de torneio.

Cruzamento (também conhecido como \textit{crossover}) é um operador que cria dois novos indivíduos na população (filhos) a partir da combinação de partes diferentes de dois outros indivíduos previamente selecionados (pais). Em forma de combinação típica, escolhe-se um ponto de cruzamento $m$, em que os $m$ primeiros genes de um dos pais é combinado com os demais $n-m$ genes do outro pai, resultando em um filho. Um outro filho é criado a partir da combinação dos genes que não foram selecionados anteriormente dos pais.

Mutação é a modificação da informação de um gene específico que, apesar de ter baixa probabilidade de ocorrência, é um fator de garantia da biodiversidade, evitando também a convergência prematura da solução (viés).

A \textit{função de fitness} avalia cada indivíduo da população e é utilizada na seleção de indivíduos para a próxima geração. Cada AG pode utilizar uma estratégia diferente para a definição da \textit{função de fitness}. O importante é que esta função seja capaz de classificar o quão bom e próximo o indivíduo está da solução desejada.

A roleta \cite{goldberg} é uma estratégia clássica para seleção. Sua idéia é atribuir uma probabilidade a cada indivíduo, utilizando a proporção do seu valor de \textit{fitness} em relação ao valor total de \textit{fitness} da população.  Assim, é sorteado um número aleatório e, em seguida, verifica-se se o indivíduo é escolhido para a próxima geração ou não.

Na seleção por torneio, um grupo de indivíduos é selecionado, e um duelo ocorre entre os indivíduos selecionados. Aqueles com melhor valor da \textit{função de fitness} é selecionado para a nova população resultante.

\subsection{Algoritmo de Busca Guloso}

O algoritmo de busca guloso é um algoritmo que escolhe sempre a melhor solução local em cada passo, em função apenas da heurística adotada, para tentar chegar ao máximo global~\cite{cormen}. Ele não garante achar a solução ótima, mas é bastante utilizado, pois possui fácil implementação e geralmente se aproxima do máximo global.

